/*
 * @lc app=leetcode.cn id=2218 lang=typescript
 *
 * [2218] 从栈中取出 K 个硬币的最大面值和
 */

// @lc code=start
function maxValueOfCoins(piles: number[][], k: number): number {
  const n = piles.length;
  // dp[i][j] 表示前 i 个栈，能取 j 次的最大值
  const dp: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= k; j++) {
      // 当前栈不选择
      dp[i][j] = dp[i - 1][j];
      let val = 0;
      // 当前栈选择硬币，遍历选择一个值最大的且不超过 j 次
      for (let x = 1; x <= piles[i - 1].length; x++) {
        val += piles[i - 1][x - 1];
        if (x > j) break;
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - x] + val);
      }
    }
  }

  return dp[n][k];
}
// @lc code=end
